//给定一个包含红色、白色和蓝色、共 n 个元素的数组
// nums ，原地对它们进行排序，使得相同颜色的元素相邻，并按照红色、白色、蓝色顺序排列。 
//
// 我们使用整数 0、 1 和 2 分别表示红色、白色和蓝色。 
//
// 
// 
//
// 必须在不使用库内置的 sort 函数的情况下解决这个问题。 
//
// 
//
// 示例 1： 
//
// 
//输入：nums = [2,0,2,1,1,0]
//输出：[0,0,1,1,2,2]
// 
//
// 示例 2： 
//
// 
//输入：nums = [2,0,1]
//输出：[0,1,2]
// 
//
// 
//
// 提示： 
//
// 
// n == nums.length 
// 1 <= n <= 300 
// nums[i] 为 0、1 或 2 
// 
//
// 
//
// 进阶： 
//
// 
// 你能想出一个仅使用常数空间的一趟扫描算法吗？ 
// 
//
// Related Topics 数组 双指针 排序 👍 1661 👎 0


package LeetCode.editor.cn;

/**
 * @author ldltd
 * @date 2023-09-19 23:23:32
 * @description 75.颜色分类
 */
public class SortColors{
	 public static void main(String[] args) {
	 	 //测试代码
	 	 Solution solution = new SortColors().new Solution();

	 }
	 
//力扣代码
//leetcode submit region begin(Prohibit modification and deletion)
class Solution {
		 /*
		 * 1.sort  时间onlogn
		 * 2.计数排序 空间On时间on
		 * 3.先移0再移2，on  两次
		 * 4.先移0和12，再移12 on 两次
		 * 5.计数一趟
		 * num2走了全程，num1走了num0+num1的个数，num0就只走了num0的个数
		 * 而且不会被覆盖
		 * */
		 public void sortColors(int[] nums) {
			 int num0 = 0, num1 = 0, num2 = 0;
			 for(int i = 0; i < nums.length; i++) {
				 if(nums[i] == 0) {
					 nums[num2++] = 2;
					 nums[num1++] = 1;
					 nums[num0++] = 0;
				 }else if(nums[i] == 1) {
					 nums[num2++] = 2;
					 nums[num1++] = 1;
				 }else {
					 nums[num2++] = 2;
				 }
			 }
		 }

		 /*双指针 p0指向0 p1指向1*/
		 public void sortColors1(int[] nums) {
			 int n = nums.length;
			 int p0=0,p1=0;
			 for (int i = 0; i < n; i++) {
				 if(nums[i]==1){
					 int t=nums[i];
					 nums[i]=nums[p1];
					 nums[p1]=t;
					 ++p1;
				 }else if(nums[i]==0){
					 int t=nums[i];
					 nums[i]=nums[p0];
					 nums[p0]=t;
					 //找到0交换的时候，p0此时可能指向1
					 //所以如果p0<p1 还需要把nums[i]和nums[p1]交换
					 if(p0<p1){
						  t=nums[i];
						 nums[i]=nums[p1];
						 nums[p1]=t;
					 }
					 ++p0;
					 ++p1;
				 }
			 }
		 }
	/*双指针 p0->0 p2->2  p2初始值为n-1*/
	public void sortColors2(int[] nums) {
		int length = nums.length;
		int p2=length-1;
		int p0=0;
		for (int i = 0; i < length; i++) {
			//如果为2，交换后可能还是2，也可能是0，如果是0就换0，是1就不管
			while (i<=p2&&nums[i]==2){
				int t=nums[i];
				nums[i]=nums[p2];
				nums[p2]=t;
				--p2;
			}
			if(nums[i]==0){
				int t=nums[i];
				nums[i]=nums[p0];
				nums[p0]=t;
				p0++;
			}
		}
	}
	//记录每个0,1,2当前维护的末尾
	//先统一赋值成2，如果当前插入的是1，则执行覆盖1，如果是0，再执行覆盖0
	// 22222   111122  001122
	public void sortColors3(int[] nums) {
		int p0 = 0;
		int p1 = 0;
		for (int i = 0; i < nums.length; i++) {
			int x = nums[i];
			nums[i] = 2;
			if (x <= 1) {
				nums[p1++] = 1;
			}
			if (x == 0) {
				nums[p0++] = 0;
			}
		}
	}

}
//leetcode submit region end(Prohibit modification and deletion)

}
